# 二叉树的完全性检验: https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree/

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


from collections import deque
class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        """ 层序遍历每个节点， 最后得到的总和 要等于最后的编号 """
        d = deque()
        d.append((root, 1))
        n = 0
        end = 0
        while d:
            length = len(d)
            for i in range(length):
                node = d.popleft()
                
                if node[0].left: d.append((node[0].left, node[1]*2))
                if node[0].right: d.append((node[0].right, node[1]*2 + 1))

                if i == length - 1:
                    end = node[1]
                n += 1

        print(n, end)
        return n == end
